动态规划进阶篇1---背包问题
点击上方👆👆关注我
动态规划进阶篇1—-背包问题
大家好，这次给大家分享的题会比以往难一点，
学会了这道题的解题思想，对动态规划的掌握
就更上一层楼了下面先给大家讲有关于动态规划的两个概念（其实在上两次的题中我们一直有在用）
最优子结构
对于一个问题，我们可以拆分成很多相似的子问题，并且要算出原问题的最优解之前，必须先算出子问题的最优解。例如跳台阶的那道题，f(n-1),f(n-2)…这些就是子问题，我们要算出f(n)之前，就必须先算出f(n-1),f(n-2)。状态
所谓的状态就是指这个问题解决了没有（包括子问题）。我们用1表示已解决，用0表示未解决（这个用什么数字表示都行）。例如当我们求出了f(n-1)时，就把它的状态记录为1，否则记录为0。记录状态主要是为了防止大量的重复求解。然后下次计算之前，先查看是否该函数是否已经算过
问题：
给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装
入背包中物品的总价值最大?
个人感觉这道经典的0-1背包问题还是挺难的，
反正当时看了好几遍才看懂，才理解它的做法解析：
当然，对于这道题，如果你想要暴力递归的方法做也是可以的。例如我们可以把所有物品看出一个集合，然后把所有子集都求出来，然后看看那个集合的物品装的下且价值最高。不过时间复杂度是2的n次方。指数增长的复杂度自己掂量。
暴力递归的做法如下(C++)（我就不带大家找递归结束等条件了）
int n, C;//n表示物品的数量，C表示背包能承载的重量 int v[Max_n+1], w[Max_n+1];//v[i]表示地i个物品的价值，w[i]表重量 //从第i个物品挑选总重量小于j的部分 //**下标从1开始** int solve(int i, int j){ int sum; if(i > n){//已经没有物品了（因为下标从1开始的） sum = 0; }else if(j < w[i]){ //这个物品装不下 sum = solve(i+1, j);//挑选下一个物品 }else{ //物品装的下 //分是否挑选物品两种情况 //不装，则尝试挑选 下一个 //装的话，背包容量变为j-w[i],单价值多了v[i] sum = max(solve(i+1, j), solve(i+1, j-w[i])+v[i]);
return sum; } } int main(){ int sum = solve(n, C); }重复算了同一个函数很多遍，如下图
所用数据n=4,C=5,(w,v)={(2,3),(1,2),(3,4),(2,2)};
大家可以尝试用下把solve(i,j)这个函数是否算过的状态保存起来，然后计算之前先查看是否已经算过。如果算过则直接返回。递归式的动态规划就不带大家做了,主要是多接触下其他做法勒，题就要多做才能熟能生巧
下面介绍用递推式的动态规划
数据变量说明：
对于一种物品，要么装入背包，要么不装。所以对于一种物品的装入状态可以取0和1.我们设物品i的装入状态为xi,xi∈ (0,1)。
数据：物品个数n=5,物品重量w[n]={0，2，2，6，5，4},物品价值V[n]={0，6，3，5，4，6},C=10，（为了方便说明，小标从1开始）
对于m(i,j)就表示可选物品为i…n背包容量为j(总重量)时背包中所放物品的最大价值。
建立如下方格图（其实就是一个二维数组）
过程如下
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
代码如下（C++）
nt solve(int m[][11],int w[],int v[],int n)//n代表物品的个数
{
//采用从底到顶的顺序来设置m[i][j]的值
//首先放w[n]
for(int j = 0; j <= c; j++){
if(j < w[n]) m[n][j] = 0; //j小于w[n],放不下，把所对应的值设为0，否则就为可以放置
else m[n][j] = v[n];
}
//对剩下的n-1个物品进行放置。
int i;
for(i = n-1; i >= 1; i--){
for(int j = 0; j <= c; j++)
if(j < w[i]) {
m[i][j] = m[i+1][j];//如果j < w[i]则，表示放不下，它等于上一个位置的值。
}else {
//否则，就考虑是否要放置，原理和递归做法相似
m[i][j] = max(m[i+1][j], m[i+1][j-w[i]] + v[i]);
}
return m[1][c];//m[1][c]就是所求最大值
}动态规划的实质就是，将问题化为求解子问题，前一个子问题最值问题求解了，如果你找到子问题与当前问题的关系，那么当前问题就解决了，是一个迭代的过程。
另外，将搜索进行记忆化，也就是说把算过的记录起来。下面给大家推荐一道类似的题，做法和这个背包的几乎一样，考考大家，给大家练练手。
问题描述：
小明是一个喜欢看动画片的人，自从成为ACMer（ACM爱好者）之后，他又迷上了网上做题。做题让他快乐，不过这也是需要付出精力的！！
假设有n道题，Lian做出第i道题后，他可以获得的快乐指数将增加gethappy[i]，而消耗掉的精力将是losspow[i]。
假设Lian初始的快乐指数为1，精力为2000。可以理解，如果他消耗完了所有的精力那他得到再多的快乐都没有用。
你的任务就是帮他计算他所能得到的最多的快乐指数，且最后他依然有多余的精力（即至少为1）。
输入格式
第一行输入一个整数n，表示有n个人。(n<=50)
第二行输入n个整数，表示gethappy[1]到gethappy[n]
第三行输入n个整数，表示losspow[1]到losspow[n]。输出格式
一个整数，表示小明所能获得的最大快乐指数。输入样例
3
15 23 61
350 1301 1513输出样例
77希望大家能有所收获。
下次会给大家推荐一些数据结构与算法的书（都是自己看过的，感觉还不错）。
如果大家想要这道题的答案，可以在公众号回复小明的快乐获取。
你们的支持便是我最大的动力，支持就关注我的公众号吧：di201805
下面二维码